'''
https://leetcode.cn/problems/the-maze-ii
'''
import heapq
from collections import deque
from typing import List


class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        destination = tuple(destination)
        m, n = len(maze), len(maze[0])
        visited = [[False] * n for _ in range(m)]
        distance = [[float('inf')] * n for _ in range(m)]
        distance[start[0]][start[1]] = 0
        pq = [(0, start[0], start[1])]
        while pq:
            cost, i, j = heapq.heappop(pq)
            if (i, j) == destination: return cost
            if visited[i][j]: continue
            visited[i][j] = True
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                cur_cost = 0
                x, y = i + dx, j + dy
                while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
                    cur_cost += 1
                    x, y = x + dx, y + dy
                x, y = x - dx, y - dy
                if cur_cost + cost < distance[x][y]:
                    distance[x][y] = cur_cost + cost
                    heapq.heappush(pq, (cur_cost + cost, x, y))
        return -1